//79 字母矩阵搜索
/*
给定一个字母矩阵，所有的字母都与上下左右四个方向上的字母相连。给定一个字符串，求
字符串能不能在字母矩阵中寻找到

输入输出样例：
	输入是一个二维字符数组和一个字符串，输出是一个布尔值，表示字符串是否可以被寻找
到
Input: word = "ABCCED", board =
[['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']]
Output: true

*/
// 主函数
bool exist(vector<vector<char>> &board, string word)
{
	if (board.empty())
		return false;
	int m = board.size(), n = board[0].size();
	vector<vector<bool>> visited(m, vector<bool>(n, false)); //访问标记
	bool find = false;
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j) //
		{
			backtracking(i, j, board, word, find, visited, 0);
		}
	}
	return find;
}
// 辅函数
void backtracking(int i, int j, vector<vector<char>> &board, string &word, bool &find, vector<vector<bool>> &visited, int pos)
{
	if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size())
	{
		return;
	}
	if (visited[i][j] || find || board[i][j] != word[pos])
	{
		return;
	}
	if (pos == word.size() - 1)
	{
		find = true;
		return;
	}
	visited[i][j] = true; // 修改当前节点状态
	// 递归子节点
	backtracking(i + 1, j, board, word, find, visited, pos + 1);
	backtracking(i - 1, j, board, word, find, visited, pos + 1);
	backtracking(i, j + 1, board, word, find, visited, pos + 1);
	backtracking(i, j - 1, board, word, find, visited, pos + 1);
	visited[i][j] = false; // 回改当前节点状态
}
